package subString;

public class LeetCode_28 {
    public int strStr(String haystack, String needle) {
        return stringMatch(haystack,needle);
    }

    /**
     * 求解next数组--暴力法
     * @param str 待匹配字符串
     * @return next数组
     */
    public int[] getNext_1(String str) {
        //1. 定义next数组
        int n = str.length();
        int[] next = new int[n];
        //2. 对于0位置的判定
        if (n==0){
            return next;
        }else if (n==1){
            next[0]=-1;
            return next;
        }else {
            next[0]=-1;
            next[1]=0;
        }
        //3. 对于其他位置的判定
        for (int i = 2; i < n; i++) {
            //3.1 默认为0
            next[i] = 0;
            //3.2 循环求解最大next值
            for (int j = i-1; j >= 1 ; j--) {
                //3.2.1 判断当前长度的前后字串是否相同
                if (str.substring(0,j).equals(str.substring(i-j,i))){
                    next[i] = j;
                    break;
                }
            }
        }
        return next;
    }

    /**
     * 求解next数组--动态规划法
     * @param str 待匹配字符串
     * @return next数组
     */
    public int[] getNext_2(String str) {
        //1. 定义next数组
        int n = str.length();
        int[] next = new int[n];
        //2. 对于0位置的判定
        if (n==0){
            return next;
        }else if (n==1){
            next[0]=-1;
            return next;
        }else {
            next[0]=-1;
            next[1]=0;
        }
        //3. 对于其他位置的判定
        for (int i = 2; i < n; i++) {
            //3.1 定义tempIndex
            int tempIndex = i-1;
            //3.2 循环求解next值
            while(true){
                if (str.charAt(i-1)==str.charAt(next[tempIndex])){
                    next[i] = next[tempIndex]+1;
                    break;
                }else{
                    tempIndex = next[tempIndex];
                }
                if (next[tempIndex]==-1){
                    next[i]=0;
                    break;
                }
            }

        }
        return next;
    }



    /**
     * 求解index--KMP算法
     * @param arr 待匹配字符串
     * @param str 待匹配子串
     * @return 匹配成功的位置
     */
    public int stringMatch(String arr,String str){

        //1. 定义变量
        int i=0,j=0;
        int[] next = getNext_2(str);
        //2. 循环匹配
        while (i<arr.length()&&j<str.length()){
            //2.1 逐字符判断
            if (arr.charAt(i)==str.charAt(j)){
                i++;
                j++;
            }else{
                j = next[j];
                if (j==-1){
                    i++;
                    j=0;
                }
            }
        }
        //3. 判断是否匹配成功
        if (j==str.length()){
            return i-j;
        }
        return -1;
    }


    public int findStringIndex(String arr, String str) {
        //1. 定义变量，记录匹配的字符串的下标
        int i=0,j=0;
        //2. 遍历数组，逐个元素与目标字符串进行匹配
        while(i<arr.length() && j<str.length()){
            if(arr.charAt(i)==str.charAt(j)){
                i++;
                j++;
            }else{
                i=i-j+1;
                j=0;
            }
        }
        //3. 返回
        if(j==str.length()){
            return i-j;
        }
        return -1;
    }
}
